package arrAndstr;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/*
	101. 对称二叉树
		中序遍历+栈
 */
public class T101 {

	public static class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode() {
		}

		TreeNode(int val) {
			this.val = val;
		}

		TreeNode(int val, TreeNode left, TreeNode right) {
			this.val = val;
			this.left = left;
			this.right = right;
		}
	}

	public static void main(String[] args) {
		TreeNode root = new TreeNode(1);
		root.left = new TreeNode(2);
		root.left.left = new TreeNode(2);
//		root.left.right = new TreeNode(4);
		root.right = new TreeNode(2);
		root.right.left = new TreeNode(2);
//		root.right.right = new TreeNode(3);

		System.out.println(isSymmetric(root));
	}

	public static boolean isSymmetric(TreeNode root) {
		// 左 LDR， 右 RDL --> 判断每个是否相同
		return searchTwo(root.left, root.right);
	}

	private static boolean searchTwo(TreeNode left, TreeNode right) {
		if (left ==null && right==null)	return true;
		if (right==null || left==null)	return false;

		return left.val==right.val && searchTwo(left.left, right.right) && searchTwo(left.right, right.left);
	}

}
